1. Field of the Invention
The present invention relates to a recognition device, a recognition method, and a program, and more particularly, to a recognition device, a recognition method, and a program, which can rapidly perform the matching of a feature point set selected from a model image and a feature point set selected from a query image with each other.
2. Description of the Related Art
As a general object recognition scheme by using a local feature amount, Japanese Unexamined Patent Application Publication No. 2008-77625 discloses a scheme in which a plurality of feature point sets including a base point and a single or a plurality of support points, respectively, is extracted from the model image and the query image, and the matching of feature point sets with each other is performed.
For example, the base point of the model image is a feature point serving as a reference among feature points set up on the model image, and the support point is a feature point other than the base point and is determined in dependence to the base point. At the time of modeling, information representing a feature amount of each of the feature points and geometric information that is information representing a position of each support point, with a position of the base point given as a reference, are made to be stored.
According to the scheme (hereinafter, referred to as “scheme in the related art”) disclosed in Japanese Unexamined Patent Application Publication No. 2008-77625, the recognition of an object of little texture may be robustly performed or the recognition may be performed, with an influence of a background being suppressed.
For a practical realization of the scheme in the related art, the speeding up of a calculation is necessary. For example, as a scheme of realizing the speeding up of the object recognition by using the local feature amount, there is a method of performing a database search represented by LSH (Locality Sensitive Hashing) disclosed in ‘Locality-sensitive hashing scheme based on p-stable distributions’, Mayur Datar, Piotr Indyk, Proceedings of the twentieth annual symposium on Computational geometry, pp. 253-262, 2004.
In the LSH, when a feature point of a query image is input, a cluster of model feature point, which is a subset to which the feature point belongs, is specified, and a similarity degree is calculated only with respect to the model feature point included in the same cluster. An amount of calculation is made to be small by decreasing the number of similarity degree calculations compared to a nearest search in which the similarity degree between all feature points is calculated, such that the recognition of an object may be rapidly performed.
A scheme in which the matching of the feature point in a feature point set unit is realized by using a hypergraph is disclosed in ‘A Tensor-Based Algorithm for High-Order Graph Matching’, Olivier Duchenne, Francis Bach, Inso Kweon, Jean Ponce, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009.